Aaron Potechin
The planted clique problem asks whether or not we can find a k-clique which is planted in a random G(n,1/2) graph. Although the expected size of the largest clique in a random graph is only 2lg(n), we currently do not know of any polynomial time algorithm which can find a planted clique of size much smaller than n^(1/2).
One potential method of solving the planted clique problem is the sum of squares hierarchy. The sum of squares hierarchy is one of the most powerful tools for approximation algorithms that we know of, capturing algorithms such that the Goemmans-Williamson algorithm for max-cut, the Arora-Rao-Vazirani algorithm for sparsest cut, and the Arora-Barak-Steurer subexponential algorithm for unique games. However, its performance on many problems is not well understood. Until recently there were no non-trivial bounds on the performance of the sum of squares hierarchy on the planted clique problem.
In this talk, I will present almost tight lower bounds for the sum of squares hierarchy on the planted clique problem, describing the planted clique problem, the sum of squares hierarchy, and how we can show that the sum of squares hierarchy fails to find the planted clique if its size k is much smaller than n^(1/2).